package 算法.其他算法;

public class JZ62孩子们的游戏_圆圈中最后剩下的数_ {
    //约瑟夫环环问题
    //递归
    public int LastRemaining_Solution(int n, int m) {
        if(n==0 || m==0)
            return  -1;
        return function(n, m);
    }
    int function(int n, int m){
        if (n == 1)
            return 0;
        //递归
        int x = function(n-1,m);
        //返回最后删除的那个元素
        return  (m + x) % n;
    }

    //迭代
    public int LastRemaining_Solution2(int n, int m) {
        //没有小朋友的情况
        if(n == 0 || m == 0)
            return -1;
        int x = 0;
        //从小到大，更新x
        for(int i=2;i<=n;i++)
            x = (m+x) % i;
        return  x;
    }
}
